package dynamicPrograming.钢条切割;

public class dpTopToBottom {

    public static int cut_road(int[] p ,int n ){
        int[] r = new int[p.length+1];

        for( int i = 1 ; i < r.length ; i++ ){
            r[i] = Integer.MIN_VALUE;
        }

        return cut( p , n , r );
    }

    public static int cut(int[] p , int n , int[] r ){
        if(r[n]>0){
            return r[n];
        }
        if(n==0){
            return 0;
        }

        int q = Integer.MIN_VALUE;
        for( int i = 1 ; i <= n ; i++){
            q = Math.max( q , p[i] + cut( p , n-i , r ));
        }
        return q;
    }

    public static void main(String[] args) {
        int[] p = new int[]{0,1,5,8,9,10,17,17,20,24,30};
        System.out.println(cut_road(p,10));
    }

}
